"""
广度优先搜索 (Breadth-First Search, BFS) 算法实现

该模块实现了一个简单的广度优先搜索算法，用于在图中查找特定条件的节点。
在这个例子中，我们查找名称以 'm' 结尾的芒果销售商。

示例用法:
    python BFS.py
"""

from collections import deque
from typing import Dict, List, Set, Optional
import logging

# 配置日志
logging.basicConfig(
    level=logging.INFO,
    format='%(asctime)s - %(name)s - %(levelname)s - %(message)s'
)
logger = logging.getLogger(__name__)

# 图的表示，使用字典字面量初始化，代码更简洁
# 键是人名，值是该人的朋友列表
graph: dict[str, list[str]] = {
    "you": ["alice", "bob", "claire"],
    "bob": ["anuj", "peggy"],
    "alice": ["peggy"],
    "claire": ["thom", "jonny"],
    "anuj": [],
    "peggy": [],
    "thom": [],
    "jonny": []
}

def person_is_seller(name: str) -> bool:
    """
    判断一个人是否为芒果销售商
    
    Args:
        name: 人的名字
        
    Returns:
        如果名字以 'm' 结尾，则返回 True, 否则返回 False
    """
    return name.endswith('m')  # 使用 endswith 方法提高可读性

def search(graph: Dict[str, List[str]], start_name: str, 
           is_target_func=person_is_seller) -> Optional[str]:
    """
    在图中使用广度优先搜索算法查找目标节点
    
    Args:
        graph: 表示图的字典，键是节点名，值是相邻节点列表
        start_name: 开始搜索的节点名称
        is_target_func: 判断节点是否为目标的函数，默认为 person_is_seller
        
    Returns:
        如果找到目标，返回目标节点名称；否则返回 None
        
    Raises:
        KeyError: 如果起始节点不在图中
    """
    if start_name not in graph:
        raise KeyError(f"起始节点 '{start_name}' 不在图中")
    
    # 创建搜索队列，初始包含起始节点的所有邻居
    search_queue = deque(graph[start_name])
    logger.debug(f"初始队列: {list(search_queue)}")
    
    # 用于记录已搜索过的节点，避免重复搜索
    # 将起始节点加入已搜索集合，因为我们已经将其邻居加入队列
    searched: Set[str] = {start_name}
    
    # 记录搜索路径
    path_to: Dict[str, str] = {neighbor: start_name for neighbor in graph[start_name]}
    
    while search_queue:
        current = search_queue.popleft()  # 取出队列中的第一个节点
        logger.debug(f"当前处理节点: {current}")
        
        if current not in searched:
            logger.debug(f"检查节点: {current}")
            
            # 检查当前节点是否为目标
            if is_target_func(current):
                # 构建从起始节点到目标节点的路径
                path = []
                node = current
                while node != start_name:
                    path.append(node)
                    node = path_to[node]
                path.append(start_name)
                path.reverse()
                
                logger.info(f"找到目标 '{current}'! 路径: {' -> '.join(path)}")
                return current
            
            # 将当前节点的所有未搜索过的邻居加入队列
            for neighbor in graph[current]:
                if neighbor not in searched and neighbor not in search_queue:
                    search_queue.append(neighbor)
                    # 记录到达邻居节点的前一个节点
                    path_to[neighbor] = current
            
            # 标记当前节点为已搜索
            searched.add(current)
    
    logger.info("未找到目标节点")
    return None

def main():
    """主函数，程序入口点"""
    try:
        result = search(graph, "you")
        if result:
            print(f"找到芒果销售商: {result}")
        else:
            print("没有找到芒果销售商")
    except KeyError as e:
        logger.error(f"错误: {e}")
        print(f"错误: {e}")

if __name__ == "__main__":
    main()
